package com.codingvip.dynamic;

public class MinDist {
    private int[][] matrix= {
        {1,3,5,9},
        {2,1,3,4},
        {5,2,6,7},
        {6,8,4,3}
    };
    private int n=4;
    private int[][] mem = new int[4][4];

    public int minDist(int i,int j) {
        System.out.println("QIU:i=" + i + ",j=" + j);
        if (i == 0 && j == 0) {
            mem[0][0]=matrix[0][0];
            return matrix[0][0];
        }
        if (mem[i][j] > 0) {
            return mem[i][j];
        }
        int minLeft = Integer.MAX_VALUE;
        if (j - 1 >= 0) {
            minLeft=minDist(i, j - 1);
        }
        int minUp = Integer.MAX_VALUE;
        if (i - 1 >= 0) {
            minUp=minDist(i-1, j );
        }
        int curentMinDist = Math.min(minUp, minLeft) + matrix[i][j];
        mem[i][j] = curentMinDist;
        System.out.println("输出：currentMinDist:"+curentMinDist);
        return curentMinDist;
    }

    public static void main(String[] args) {
        MinDist minDist = new MinDist();
        int result = minDist.minDist(3, 3);
        System.out.println(result);
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                System.out.print(minDist.mem[i][j]+", ");
            }
            System.out.println("");

        }




    }
}
